//
//  Vector_search.swift
//  SwiftyDSA
//
//  Created by Archer on 2018/8/6.
//  Copyright © 2018年 Archer. All rights reserved.
//

import Foundation

extension Vector where Element: Comparable {
    
    public func search(_ element: Element) -> Index {
        return _search(element, from: 0, to: _size)
    }
    
    public func search(_ element: Element, at range: CountableRange<Index>) -> Index {
        return _search(element, from: range.lowerBound, to: range.upperBound)
    }
    
    public func search(_ element: Element, at range: CountableClosedRange<Index>) -> Index {
        return _search(element, from: range.lowerBound, to: range.upperBound.advanced(by: 1))
    }
    
    /// 有序向量查找
    /// 返回不大于element的最后一个元素
    func _search(_ element: Element, from startIndex: Index, to endIndex: Index) -> Index {
        precondition(startIndex >= 0 && startIndex <= endIndex, "Index不能为负数且startIndex不能大于endIndex")
        precondition(endIndex <= self.endIndex, "指定区间(\(startIndex)-\(endIndex))超过\(self)的容量")
        #if false
        // 不满足语义要求 找不到指定元素时只是简单返回-1
        var start = startIndex
        var end = endIndex
        while start < end {
            let mid = ((end + start).toDouble() / 2).toInt()
            // 这个地方_storage[mid]已经比较过了
            // 也就是不考虑落在mid上的元素了
            // 如果mid不满足要求 就折半区间
            if _storage[mid] < element {
                start = mid + 1 // 新区间要包含start
            } else if _storage[mid] > element {
                end = mid // 新区间也不包含end
            } else {
                return mid
            }
        }
        return NotFound
        #else
        var start = startIndex
        var end = endIndex
        while start < end {
            let mid = ((end + start).toDouble() / 2).toInt()
            // 将整个连续内存分为两段
            // 左边的元素都严格的小于等于element
            // 右边的元素都严格的大于element
            // 循环退出时 start == end
            // 也就是一个空区间 同样满足 left <= element, right > element
            // 所以start - 1就是最后一个 <= element的元素 也就是不大于element的最后一个元素
            if _storage[mid] <= element {
                start = mid + 1
            } else {
                end = mid
            }
        }
        return start - 1
        #endif
//     返回不小于element的第一个元素
//        var start = startIndex
//        var end = endIndex
//        while start < end {
//            let mid = ((end + start).toDouble() / 2).toInt()
//            if _storage[mid] < element {
//                start = mid + 1
//            } else {
//                end = mid
//            }
//        }
//        return end
    }
}
